package com.su.test;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

public class SuperAalgorithm extends Strategy{
    private int [] indexTargetArr;//记录目标数组每一元素的索引

    public SuperAalgorithm() {
    }

    public void run(){
        indexTargetArr = new int[length];
        for(int i=0;i<length;i++){
            indexTargetArr[targetArr[i]] = i;
        }
        super.steps = 0;
        //open表
        Queue<Node> openQueue = new PriorityQueue<Node>((o1, o2)->{
            if(o1.evaluation > o2.evaluation)
                return 1;
            else if(o1.evaluation < o2.evaluation)
                return -1;
            return 0;
        });

        int emptyIndex=0;     //记录空格的位置
        for (int i = 0; i < length; i++) {
            if(initArr[i] == 0){
                emptyIndex = i;
            }
        }
        int manhattanDistance = ManhattanDistance(initArr);
        Node initNode = new Node(initArr,manhattanDistance,emptyIndex,null);
        openQueue.add(initNode);
        //close表
        Set<Node> closeSet = new TreeSet<>();

        while (!openQueue.isEmpty()){
            super.steps++;      //记录步数


            Node curNode = openQueue.poll();

            //当前节点是目标节点
            if(curNode.misposition == 0){
                super.lastNode = curNode;
                long endTime = System.currentTimeMillis();
                return;
            }

            int mispositionOfCur = curNode.misposition;//当前节点“不在位”的个数
            int emptyIndexOfCur = curNode.emptyIndex;   //当前节点空格位置

            //左移
            if(emptyIndexOfCur % this.col > 0){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-1);
                manhattanDistance = ManhattanDistance(nextArr);
                Node nextNode = new Node(nextArr,manhattanDistance,emptyIndexOfCur -1,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //上移
            if(emptyIndexOfCur > this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-this.col);
                manhattanDistance = ManhattanDistance(nextArr);

                Node nextNode = new Node(nextArr,manhattanDistance,emptyIndexOfCur - this.col,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //右移
            if(emptyIndexOfCur % this.col < this.col - 1){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,1);
                manhattanDistance = ManhattanDistance(nextArr);
                Node nextNode = new Node(nextArr,manhattanDistance,emptyIndexOfCur + 1,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //下移
            if (emptyIndexOfCur < length - this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,this.col);
                manhattanDistance = ManhattanDistance(nextArr);
                Node nextNode = new Node(nextArr,manhattanDistance,emptyIndexOfCur +this.col,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }

            closeSet.add(curNode);

        }
    }

    /**
     * @Description     计算两个数组的曼哈顿距离
     * @param curArr    当前数码
     * @return      曼哈顿距离
     **/
    private int ManhattanDistance(int curArr[]){
        int indexCurArr[] = new int[length];    //记录当前数组每个元素的索引
        for(int i=0;i<length;i++){
            indexCurArr[curArr[i]] = i;
        }

        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += Math.abs(indexCurArr[i]/col - indexTargetArr[i]/col) + Math.abs(indexCurArr[i]%col - indexTargetArr[i]%col);
        }

        return sum;
    }

}
